//
//  BuildTree.swift
//  LeetCodeSummary
//
//  Created by 彭西西 on 2020/8/13.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  剑指 Offer 07. 重建二叉树

import UIKit

/*
 剑指 Offer 07. 重建二叉树
 
 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

  

 例如，给出

 前序遍历 preorder = [3,9,20,15,7]
 中序遍历 inorder = [9,3,15,20,7]
 返回如下的二叉树：

     3
    / \
   9  20
     /  \
    15   7
 */

class BuildTree: NSObject {
    
    //递归解法
    /*
     前序遍历的结果可分为  |根|左|右|
     中序遍历的结果可分为  |左|根|右|
     
     我们可以根据preorder[0]得出整个树rootNode，再根据 inorder 得出他的左右字数，然后左右递归即可。
     
     */
    
    func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
        guard preorder.count != 0 else {
            return nil
        }
        
        return self.helper(preorder, 0, inorder, 0, preorder.count-1)
    }
    
    func helper(_ preorder: [Int], _ preIndex: Int,_ inorder: [Int], _ left: Int, _ right: Int) -> TreeNode?{

        if left > right{
            return nil
        }
        
        let rootNode = TreeNode.init(preorder[preIndex])
        
        var rightIndex = 0
        
        for i in left ... right{
            if inorder[i] == rootNode.val {
                rightIndex = i
                break
            }
        }
        
        rootNode.left = self.helper(preorder,  preIndex + 1,                     inorder, left,         rightIndex-1)
        rootNode.right = self.helper(preorder, preIndex + rightIndex - left + 1, inorder, rightIndex+1, right)
                                               //这里如果传 rightIndex + 1    用例[1,2,3] [3,2,1]无法通过
        return rootNode
    }
}
